package jianzhi

import "fmt"

func pathSum(root *TreeNode, target int) [][]int {

	path := []int{}
	res := [][]int{}

	var dfs func(*TreeNode, int)
	dfs = func(node *TreeNode, val int) {

		if node == nil {
			return
		}

		path = append(path, node.Val)

		fmt.Println(path, target)

		dfs(node.Left, val-node.Val)

		dfs(node.Right, val-node.Val)

		if node.Left == nil && node.Right == nil && node.Val == target {
			res = append(res, append([]int(nil), path...))
		}

		path = path[:len(path)-1]

	}

	dfs(root, target)

	return res

}
